package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

/**
 * 猜数字
 * yes!
 *
 * @author tzp
 * @since 2020/9/21
 */
public class LC375_3 implements DynamicProblem {
    public int getMoneyAmount(int n) {
        int[][] dp = new int[n + 1][n + 1];//猜测start,step这些数所需要付出的minmax的惩罚
        for (int step = 1; step <= n; step++) {
            for (int start = 1; start <= n; start++) {
                if (start + step - 1 > n) {
                    break;
                }
                if (step == 1) {
                    dp[start][step] = 0;
                } else if (step == 2) {
                    dp[start][step] = start;
                } else {
                    int min = Integer.MAX_VALUE;
                    for (int i = 0; i < step; i++) {
                        int mid = start + i;
                        int left = i == 0 ? 0 : dp[start][i];
                        int right = i == step - 1 ? 0 : dp[start + i + 1][step - i - 1];
                        min = Math.min(min, mid + Math.max(left, right));
                        //min = Math.min(min, mid + left + right);//fuck 不是mid+left+right, 是取个max
                    }
                    dp[start][step] = min;
                }
            }
        }
        for (int i = 1; i < n; i++) {
            System.out.println(i + " " + dp[1][i]);
        }
        return dp[1][n];
    }

    public static void main(String[] args) {
//        System.out.println(new LC375_3().getMoneyAmount(6));//8
//        System.out.println(new LC375_3().getMoneyAmount(7));//10
        System.out.println(new LC375_3().getMoneyAmount(100));//21
    }
}
